The transmission of electronic data via facsimile machines and similar devices has become quite common. Efforts to transmit significantly larger volumes of this data within a substantially shortened period of time are constantly being made. This is true not only to allow for data to be sent from one location to another at faster speeds and thereby causing less inconvenience to the user, but to enable more complex data to be transmitted between the same locations without drastically increasing the required processing time. For example the facsimile processing time for a detailed halftoned image will be many times more than that of a simple sheet of black text on a white page when using the same fax machine. By the same token, fax processing of a color image will require an even greater amount of time than its greatly detailed halftoned counterpart.
Without any form of processing reduction, color image data files via facsimile would require extensive resourcesxe2x80x94very large buffers for one examplexe2x80x94and would still take a great deal of processing time, thereby causing receipt of such transmission to become very lengthy and expensive and therefore, impractical. The transmission of color image data via fax is typically accomplished using some form of data compression prior to transmission. The JPEG (Joint Photographic Experts Group) standard provides a well known method of compressing electronic data. JPEG uses the discrete cosine transform (DCT) to map space data into spatial frequency domain data. Simply put, the first step in JPEG compression is to transform an 8xc3x978 block of pixels into a set of 8xc3x978 coefficients using the DCT. In a block, the DCT coefficient with the lowest frequency is referred to as the DC coefficient (DCC), and the remaining coefficients are AC coefficients (ACCs). The DCC and ACCs are quantizedxe2x80x94divided by an integer referred to as the xe2x80x9cstep sizexe2x80x9d and rounded to the nearest whole number. The losses that occur during JPEG compression typically occur during the quantization step. The magnitude of this loss is obviously dependent upon the step size selected and the resulting amount of round-off required to perform quantization.
Next, the quantized coefficients are arranged in a one dimensional vector by following a selected path (i.e. zigzag) through the 8xc3x978 block of quantized coefficients. The DCC is typically the first value in the vector. Ordinary JPEG compression typically includes replacing the quantized DCC with the difference of its actual value minus the DCC of the previous block, to provide a differential DCC. Finally, the vector is encoded into a bit stream through a sequence of Run Length Counting (RLC) operations, combined with Variable Length Codes (VLC) to produce a compressed data stream.
The xe2x80x9creceivingxe2x80x9d portion of a fax transmission, after storage of the incoming data in a buffer, applies the inverse of the JPEG operations utilized in the sending portion. First, VLD/RLD decoding operations are performed to decompress the data stream, followed by a inverse DC DPCM operation to recover the DC component of the coefficient matrix. The resulting serial data is then arranged in a 8xc3x978 matrix using the inverse zig-zag pattern. An inverse quantization is then performed. That result is then subjected to an inverse 8xc3x978 discrete cosine transformation to yield the output image. Considerable processing time must be budgeted for the inverse 8xc3x978 discrete cosine transform.
Color image data is complex, so high compression ratios must usually be applied in order to complete the transmission within an acceptable time frame. High compression ratios lead to more data loss, which typically occurs at the higher end of the frequency range. Further, the imaging devices typically included with fax machines in the lower end of the market usually include thermal ink-jet printers and would likely use error diffusion halftoning techniques. The halftoning that occurs when using a thermal ink jet printer results in an additional loss of high frequency data. Thus, much of the detail in the original image that is preserved and transmitted will never actually be viewed by the ultimate user.
With this in mind, successful fax transmission requires a proper correspondence between the decompression operation being applied to the image data and the clock speed of CPU of the receiving fax. In other words, if the decompression operation requires to much processing for a given CPU speed the data will have to wait for reception, and an appropriately sized buffer will be required. This will also frustrate the human operator if it delays the printing of a color fax too much and if the phone line wait times become to long because of buffer overflow, the transmission will be terminated. Thus, it is advantageous to reduce processing time at the receiving fax. One way to do this is obviously to implement a faster CPU to keep the data moving through the modem. Further, a larger buffer may be provided to avoid wait time in the phone line transmission. However, these solutions result in significant cost increases and may even be impractical. Thus, it is most advantageous to shorten the computational processing time of a color facsimile by implementing a faster data decompression without having to resort to the purchase of more expensive equipment.
The following disclosures may be relevant to aspects of the present invention:
U.S. Pat. No. 5,737,450 to Hajjahmad et al. issued Apr. 7, 1998 discloses a method and apparatus for applying an image filter to an image signal where image data terms, corresponding to the image signal, are converted by means of an overlapping operation and a scaled forward orthogonal transformation to form frequency coefficient matrices, the image filter is converted by means of a descaled orthogonal transformation to form a descaled frequency filter matrix, and the frequency coefficient matrices are multiplied by the descaled frequency filter matrix to form filtered coefficient matrices for conversion into a filtered image signal by means of an inverse orthogonal transformation process.
U.S. Pat. No. 5,699,170 to Yokose et al. issued Dec. 16, 1997, discloses an image communication system wherein transmission of an image between an image transmission apparatus and an image reception apparatus which include image output sections having different performances can be performed without making an inquiry for the performance prior to transmission is disclosed. An image is inputted by an image input section and sent to a hierarchization section in the image transmission apparatus. The hierarchization section converts the inputted image into hierarchic communication data and transmits hierarchized data to a selection section of the image reception apparatus. The selection section extracts only necessary data from the hierarchic communication data transmitted thereto in accordance with the performance of an image output section of the image reception section and then sends the necessary data to the image output section after, if necessary, they are converted into image data. The image output section visualize the image data transmitted thereto from the selection section.
U.S. Pat. No. 5,642,438 to Babkin issued Jun. 24, 1997 discloses image compression implementing a fast two-dimensional discrete cosine transform. More specifically, Babkin discloses a method and apparatus for the realization of two-dimensional discrete cosine transform (DCT) for an 8xc3x978 image fragment with three levels of approximation of DCT coefficients. xe2x80x9cJPEG: Still Image Compression Standardxe2x80x9d, New York, N.Y., Van Nostrand Reinhold, 1993 by W. B. Pennebaker and J. L. Mitchell.
All of the references cited herein are incorporated by reference in their entirety for their teachings.
Accordingly, although known apparatus and processes are suitable for their intended purposes, a need remains for image decompression via a fast JPEG compressor using a variable block-size inverse discrete cosine transform to decompress digital image data and shorten processing time, thereby improving the efficiency of the serial data transmission.
The present invention relates to a method of improving the speed and efficiency of electronic data decompression. This method comprises retrieving compressed serial data corresponding to a matrix. Then applying a transform to a subset of the compressed serial data to produce a subset transform result. Finally interpolation of the subset transform result is performed to provide decompressed data.
In accordance with another aspect of the invention there is provided a method of improving the speed and efficiency of electronic data decompression. This method comprises examining compressed serial data for particular arrangements of data. Then determining a subset of the compressed data depending upon the particular arrangement of data found in the examining step. This is followed by applying a transform to the subset of the compressed data to produce a subset transform result. Finally interpolation of the subset transform result is performed to provide decompressed data.
In accordance with yet another aspect of the invention there is provided a method of improving the speed and efficiency of JPEG decompression. This method comprises examining compressed serial data for particular arrangements of data to determine a determined subset of compressed data. Then applying a transform to the determined subset of compressed data to produce a subset transform result. Finally, interpolation of the subset transform result is performed to provide a full 8xc3x978 matrix of pixel data.